package 线;

import com.cc.User;

import java.util.*;

/**
 * @author ycc
 * @date 2025/6/28
 * 获取推广树-广度优先遍历
 * 把简单但重要的小事做好
 */
public class MyTree {
    public static void main(String[] args) {
        List<User> list = new ArrayList<>();
        list.add(new User(1, 0));
        list.add(new User(2, 1));
        list.add(new User(3, 2));
        list.add(new User(4, 2));
        list.add(new User(5, 3));
        list.add(new User(6, 3));
        list.add(new User(7, 0));
        list.add(new User(8, 7));

//        System.out.println(list);
        System.out.println(bfsTeam(list, 1));
        System.out.println(dfsTeam(list, 3));
        System.out.println(myTeam(list, 3, new ArrayList<>()));

    }

    /**
     * 获取所有下级推广用户id
     * @param list
     * @param id
     * @param target
     * @return
     * 采用递归方式实现深度优先遍历
     */
    public static List<Integer> myTeam(List<User> list, Integer id, List<Integer> target) {
        if (list == null || id == null) {
            return target == null ? new ArrayList<>() : target;
        }

        if (target == null) {
            target = new ArrayList<>();
        }
        for (User user : list) {
            if (user.getPid() == id) {
                target.add(user.getId());
                myTeam(list, user.getId(), target);
            }
        }
        return target;
    }

    /**
     * 获取所有下级推广用户id
     * @param list
     * @return
     * 采用深度优先遍历
     */
    public static List<Integer> dfsTeam(List<User> list, Integer id) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(id);
        while (!stack.isEmpty()) {
            Integer poll = stack.pop();
            for (User user1 : list) {
                if (user1.getPid() == poll && !visited.contains(user1.getId())) {
                    stack.push(user1.getId());
                    visited.add(user1.getId());
                    list1.add(user1.getId());
                }
            }
        }
        return list1;
    }

    /**
     * 获取所有下级推广用户id
     * @param list
     * @return
     * 采用广度优先遍历
     */
    public static List<Integer> bfsTeam(List<User> list, Integer id) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            for (User user1 : list) {
                if (user1.getPid() == poll && !visited.contains(user1.getId())){
                    queue.offer(user1.getId());
                    visited.add(user1.getId());
                    list1.add(user1.getId());
                }
            }
        }
        return list1;
    }
}
